home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / Advanced I⁄O v2.3 / Advanced i⁄o / README < prev    next >
Text File  |  1995-06-19  |  8KB  |  224 lines
  1.            Service C++ functions and classes
  2.     dealing mostly with "advanced" i/o and the arithmetic compression
  3.  
  4. ***** For the version history, read on
  5.  
  6. ***** Verification files: vendian_io, vhistogram, varithm
  7.  
  8. Don't forget to compile and run them, see comments in the Makefile for
  9. details.  The verification code checks to see that all the functions
  10. in this package have compiled and run well. The code also can serve as
  11. an example how the package classes/functions can be used
  12.  
  13. ***** Highlights and idioms
  14.  
  15. ---- Extended file names
  16.  
  17. The package adds support for "extended" file names with pipes in them.
  18. That is, the name of a file to open may be specified now as "|
  19. command" or "command |" i.e. as a pipe. For example,
  20.     EndianIn istream;
  21.     istream.open("gunzip < /tmp/aa.gz |");
  22.     EndianOut stream("| compress > /tmp/aa.Z");
  23.     image.write_pgm("| xv -");
  24. The <command> is launched in a subprocess through '/bin/sh' with its
  25. standard input/output hooked, through pipe(), to the file being
  26. opened.
  27.  
  28. This extension is implemented on the lowest possible level, right
  29. before the request to open a file goes to OS (through the system call
  30. open(2)). A function sys_open() (in the source file sys_open.cc) acts
  31. as a "patch": that is, if you call sys_open() instead of open() to
  32. open a file, you get all the open() functionality plus the extended
  33. file names.
  34.  
  35. Thus, some libg++ 2.6.2 iostream functions were modified to call
  36. sys_open() instead of open(). If one wants to use the extended file
  37. names outside gcc/libg++, he needs to do open->sys_open substitution
  38. himself.
  39.  
  40.  
  41. ---- Explicit Endian I/O of short/long integers
  42.  
  43.   EndianOut stream("/tmp/aa");
  44.   stream.set_littlendian();
  45.   stream.write_long(1);
  46.  
  47. That means, 1 would be written as a long integer with the least
  48. significant byte first, NO MATTER which computer (computer
  49. architecture) the code is running on. Using explicit endian
  50. specification (like above) is the only way to ensure portability of
  51. binary files containing arithmetic data.
  52.  
  53.  
  54. ---- Stream sharing
  55.  
  56. EndianIn/Out streams can share the same i/o buffer. This is useful
  57. when one needs to read/write a "stratified" (layered) file consisting
  58. of various variable-bit encoded data interspersed with headers.  For
  59. example, a file may begin with a header (telling the total number of
  60. data items, normalization factors) followed by some variable-bit
  61. encoding of items, followed by another header, followed by an
  62. arithmetic compressed stream of data, etc. Thus, a file can be like a
  63. waffle pie, made of many layers: each of them being interpreted using
  64. different streams, each of them collectively sharing the same file and
  65. the same file pointer. The situation is similar to sharing an open
  66. file (and a file pointer) among parent and child (forked) processes.
  67.  
  68. Note that merely opening a stream on a dup()-ed file handle, or
  69. sync()-ing the stream doesn't cut it entirely. See endian_io.cc for
  70. more discussion. The bottom line is, this package implements stream
  71. sharing in a safe and portable way: it works on a Mac just as well as
  72. on different flavors of UNIX.
  73.  
  74. ---- Simple variable-length coding of short integers
  75.  
  76. The code is intended for writing a collection of short integers where
  77. many of them are rather small in value; still, big values can crop up
  78. at times, so we can't limit the size of the code to anything less than
  79. 16 bits.  The code is a variation of a start-stop code described in
  80. Appendix A, "Variable-length representations of the integers" of the
  81. "Text Compression" book by T.Bell, J.Cleary and I.Witten,
  82. p.290-295. The present code features support for both negative and
  83. positive numbers and an optimization based on the fact that all
  84. numbers are no larger than 2^15-1 in abs value, and an assumption that
  85. most of them are smaller than 512 (in absolute value).
  86.  
  87.  
  88. ---- Arithmetic compression of a stream of integers
  89.  
  90. The present package provides a clean C++ implementation of Bell,
  91. Cleary and Witten's arithmetic compression code, with a clear
  92. separation between a model and the coder. ArithmCodingIn /
  93. ArithmCodingOut act as i/o streams that encode signed short integers
  94. you put() to, and decode them when you get() them. The
  95. ArithmCodingIn/Out object needs a "plug-in" of a class
  96. Input_Data_Model when the stream is created. The Input_Data_Model
  97. object is responsible for providing the codec with the probabilities
  98. (frequencies) a given data item is expected to appear with, and for
  99. finding a symbol given its cumulative frequency. Input_Data_Model may
  100. also modify itself to account for a new symbol. Thus, the ArithmCoding
  101. class is a sort of the 'iostream' class that writes/reads data items
  102. to/from the stream performing encoding/decoding. It relies upon the
  103. Input_Data_Model for the probabilities needed to perform the
  104. arithmetic coding.
  105.  
  106. The current version of the package provides two Input_Data_Model
  107. plug-ins, both performing adaptive "modeling" of a stream of
  108. integers. The first plug-in uses a simple 0-order adaptive prediction
  109. (like the model given in the Witten's book). The other one takes a
  110. histogram to sketch the initial distribution, and is a bit
  111. sophisticated in updating the model. It is used in compressing a
  112. wavelet decomposition of an image. The code below (taken literally
  113. from varithm.cc) demonstrates how the coder classes are actually used.
  114.  
  115. The first example writes two different streams (of different patterns,
  116. that's why it was better to encode them separately) into the same file
  117.  
  118.   EndianOut stream("/tmp/aa");
  119.   stream.set_littlendian();
  120.   const int sample_header = 12345;
  121.   {
  122.     AdaptiveModel model(-1,4);
  123.     ArithmCodingOut ac(model);
  124.     ac.open(stream);
  125.     for(i=0; i<sizeof(pattern1)/sizeof(pattern1[0]); i++)
  126.       ac.put(pattern1[i]);
  127.   }
  128.   {
  129.     stream.write_long(sample_header);    // write a "header"
  130.     AdaptiveModel model(-1,4);        // followed by the arithmetic coded
  131.     ArithmCodingOut ac(model);        // stream
  132.     ac.open(stream);
  133.     for(i=0; i<sizeof(pattern2)/sizeof(pattern2[0]); i++)
  134.       ac.put(pattern2[i]);
  135.   }
  136.   stream.close();
  137.  
  138. The reading is similar.
  139.  
  140. The second example uses a different model plug-in, yet i/o is similar
  141.  
  142. static void test_adh(void)
  143. {
  144.   message("\nCreating Histogram ...\n");
  145.   Histogram histogram(-7,7);
  146.   register int i;
  147.   for(i=0; i<MyPattern_size; i++)
  148.     histogram.put(MyPattern[i]);
  149.  
  150.   message("\nWriting data ...");
  151.   AdaptiveHistModel model(histogram);
  152.   ArithmCodingOut ac(model);
  153.   ac.open("/tmp/aa");
  154.   for(i=0; i<MyPattern_size; i++)
  155.     ac.put(MyPattern[i]);
  156.   ac.close();
  157.  
  158.   message("\nCoded file /tmp/aa has been created\n");
  159.  
  160.   AdaptiveHistModel i_model;
  161.   ArithmCodingIn ac1(i_model);
  162.   ac1.open("/tmp/aa");
  163.   for(i=0; i<MyPattern_size; i++)
  164.   {
  165.     register int val_read = ac1.get();
  166.     if( val_read != MyPattern[i] )
  167.       _error("Read value %d of the %d-th integer is not what it is "
  168.          "supposed to be, %d",
  169.          val_read, i, MyPattern[i]);
  170.   }
  171.   ac1.get();
  172.   assert( ac1.is_eof() );
  173. }
  174.  
  175. ---- Convenience Functions
  176.  
  177. The package defines a few functions I found convenient to use, like
  178. message(...) (which is equivalent to fprintf(stderr,....))  and
  179. _error(...) ( the same as message(...), abort();). One doesn't need to
  180. to #include <stdio.h> to use them.
  181.  
  182.  
  183. ***** Grand plans
  184.  
  185. ***** Revision history
  186.  
  187. Version 2.3 - Jun 1995
  188. Fixed the last remaining incompatibility glitches. Now, exactly the
  189. same code compiles on a Mac with CodeWarrior 6 and on Unix with gcc
  190. 2.6.3
  191.  
  192. Version 2.2 - May 1995
  193. Added a variable-length (start/stop) coding of signed short integers.
  194. Added dealing with simple histograms of an integer-valued
  195. distribution.
  196.  
  197. Version 2.1 - Mar 1995
  198. Introducing bool where appropriate (instead of int) and adding checks
  199. to make sure an EndianIn/Out stream was opened successfully.
  200.  
  201. Version 2.0 - Feb 1995
  202. Big change: splitting EndianIO into EndianIn and EndianOut and
  203. removing all libg++-specific things; everything should be very
  204. portable now.  Making sharing of the streambuffer portable.
  205.  
  206. Version 1.4 - Feb 1994
  207. Updated for libg++ 2.5.3
  208.  
  209. Version 1.3 - Aug 1993
  210. Introducing attachment of one stream to another, or sharing of a
  211. streambuf among several streams. Took care of properly terminating an
  212. arithm coding stream by writing a few phony bits at the end (so we
  213. won't hit the EOF on reading). Thus it is possible now to concatenate
  214. arithmetic coding streams.
  215.  
  216. Version 1.2 - Jun 1992
  217. Updated to compile under gcc/g++ 2.2.1 and work with libg++ 2.0. The
  218. first implementation of the arithmetic coding package
  219.  
  220. Version 1.1 - Nov 1991 - May 1992
  221. Initial revision
  222.  
  223.  
  224.